%----------------------------------------------------------------------------------------
%    CHAPTER 3
%----------------------------------------------------------------------------------------

\chapter{自动机基础}
%----------------------------------------------------------------------------------------
% 这章的目录3.4和3.5标反了，我写的这个顺序是正文顺序。
% 例子、定义、图的label得等大家都做完才能确定，我分别写的是undetermined_ex:n、undetermined_def:n、undetermined_fig:n。n代表我负责部分的第几个例子/定义/图
% 3.3.2节有个有限自动机化简示例，在我的第一张图上面一点，我从那部分开始转录的。 By 赫洱锋
%----------------------------------------------------------------------------------------
\section{正规语言及其描述方法}
若文法中每个产生式都限制为$A \rightarrow a B$或$A \rightarrow a $，其中A和B均为单个非终结符（此文法为右线性文法，左线性文法形如$A \rightarrow Ba$或$A \rightarrow a $），则称这类文法为正规文法。\\

\begin{definition}
    \label{def:3.1}
    正规语言是指由正规文法定义的语言。
\end{definition}

正规语言有三种等价的表示方法：

\begin{enumerate}
    \setlength{\itemindent}{2em}
    \item 正规文法 
    \item 正规式
    \item 有限自动机
\end{enumerate}

 正规文法就是正规语言的一种描述形式，正规式可以简单理解为正则表达式，是用计算机语言来描述正规语言的一种方式，这三种都是等价的。
%  \begin{figure}[H]
%     \centering
%     \input{chapter3/figures/1}
%     \caption[]{两个例子}
%     \label{fig:3.1}
% \end{figure}

\begin{example}
    \label{ex:3.1}
    正规文法$\rm{G(Z):A\rightarrow A}$|$\varepsilon$\\
    $$
        \because \mathrm{A \Rightarrow \varepsilon};\\
        \rm{A \Rightarrow a A\Rightarrow a a A\Rightarrow a a a A\Rightarrow \ldots\Rightarrow a^{n}},n \geqslant0
    $$
    正规语言$\therefore$ $\mathrm{L(G)}=\left\{a^{n} \mid n \geqslant 0\right\}$
\end{example}

\begin{example}
    \label{ex:3.2}
    $\rm{L 1=\left\{a^{m} b^{n} \mid m \geqslant 0, n \geqslant 1\right\}}$,正规语言？\\
    $\because$可由正规文法定义:\\
    $\mathrm{G 1}(\mathrm{S}): \quad \mathrm{S} \rightarrow \mathrm{aS}|\mathrm{bA} ; \mathrm{A} \rightarrow \mathrm{bA}| \varepsilon$\\
    $\therefore$ L1是正规语言
\end{example}
如果一种语言是正规语言，那就可以找到一个正规文法去描述该语言。\\

\begin{example}
    \label{ex:3.3}
    $\rm{L2 =\{(a b)^n \mid n \geqslant 1\}}$,正规语言？
    $\because$可由正规文法定义:\\
    $\mathrm{G} 2(\mathrm{~S}): \mathrm{S} \rightarrow \mathrm{aA} ; \mathrm{A} \rightarrow \mathrm{bB} ; \mathrm{B} \rightarrow \mathrm{aA} \mid \varepsilon$\\
$\therefore$L2是正规语言\\
\end{example}

\begin{example}
    \label{ex:3.4}
    $\rm{L 3=\left\{a^{n} b^{n} \mid n \geqslant 0\right\}}$,正规语言？\\
    $\because$不能由正规文法定义(正规文法无法描述a和b数量上不相等!):\\
    $\therefore$不是正规语言\\
\end{example}

用什么样的语言可以描述\\

\begin{example}
    \label{ex:3.5}
    这个文法？这个模型对应的语言需要用下推机来描述。
\end{example}

如果上下文无关文法不含有ε，则该文法可以被转化为正规文法。\\
\subsection{正规语言的正规式表示法}
$\divideontimes$正规式：是指由字母表中的符号，通过以下三种运算(也可以使用圆括号)连接起来构成的表达式 e ：连接 ( .) 或( | ) 闭包( +，* ) 
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/2}
    \caption[]{正规式举例}
    \label{fig:3.2}
\end{figure}
$\divideontimes$设 val(e),L(e) 分别表示正规式 e 的值和语言，则：L(e)={ x| x=val(e)}，即正规式表示的语言是该正规式所有值的集合(正规集)。\\
$\divideontimes$正规式表示正规语言示例：\\
%  \begin{figure}[H]
%     \centering
%     \input{chapter3/figures/3}
%     \caption[]{正规语言示例}
%     \label{fig:3.3}
% \end{figure}

\begin{example}
    \label{ex:3.6}
    (1)$\rm{e 1=a^{*} b^{+}}$\\
    $\rm{L(e 1)=\left\{a^{m} b^{n} \mid m \geqslant 0, n \geqslant 1\right\}}$;\\
    $\rm{=\{b, a b, b b, a a a b, a a b, a b b, a a b b, \ldots\}}$\\
    $\rm{(2)\ e2=(a b)^{+}}$\\
    $\rm{L(e 2)=\left\{(a b)^{n} \mid n \geqslant 1\right\},}$\\
    $\rm{=\{a b, a b a b, a b a b a b, a b a b a b a b, \ldots\}}$\\
    $\rm{(3) e 3=a b^{*} c \mid b^{*}}$\\
    $\rm{L(e 3)=\left\{a b^{n} c, \quad b^{n} \mid n \geqslant 0\right\}}$\\
    $\rm{=\{a c, a b c, a b b c, a b b b c, \ldots ; \varepsilon, b, b b, b b b, \ldots\}}$
\end{example}

\subsection{正规语言的有限自动机表示法}
有限自动机（FA）是正规语言的描述方法之一，先来看三个示例。\\
$\rm{L 1=\left\{a^{m} b^{n} \mid m \geqslant 0, n \geqslant 1\right\}}$,L1对应的有限状态自动机为
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/4}
    \caption[]{L1对应的有限状态自动机}
    \label{fig:3.4}
\end{figure}
$\rm{L2=\left\{(a b)^{n} \mid n \geqslant 1\right\}}$,L2对应的有限状态自动机为
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/5}
    \caption[]{L2对应的有限状态自动机}
    \label{fig:3.5}
\end{figure}
$\rm{L3 =\left\{a b^{n} c, b^{n} \mid n \geqslant 0\right\}}$,L3对应的有限状态自动机为
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/6}
    \caption[]{L3对应的有限状态自动机}
    \label{fig:3.6}
\end{figure}
$\divideontimes$初看起来，有限自动机是带标记的有向图！$\circledtext{1}$$\circledtext{2}$$\circledtext{3}$$\circledtext{4}$是图上的节点，称之为状态，带箭头的线可以理解为图上的边，这个边是有方向的，称之为有向边，+和-分别对应起始状态和结束状态\\
我们让大家有一个直观的印象，每一个正规语言都可以用一个有限状态自动机来描述。\\
$\divideontimes$有限自动机表示法说明：\\
$\rm{L3 =\left\{a b^{n} c, b^{n} \mid n \geqslant 0\right\}}$有限状态自动机由什么组成呢？
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/7}
    \caption[]{FA3对应自动机}
    \label{fig:3.7}
\end{figure}
我们分析一下FA3\\
【图符说明】:
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/8}
    \caption[]{符号说明}
    \label{fig:3.8}
\end{figure}
$\circledtext{1}$$\circledtext{2}$$\circledtext{3}$$\circledtext{4}$是状态，状态表示的是事物在某一时刻的表示，+和-分别表示开始状态和结束状态，自动机的运行一定要从开始状态开始，最终到达结束状态，$\circledtext{1}$代表起始状态和结束状态可以是同一个状态。\\
字母表可以理解为文法中的字母表，自动机需要读入的最基本的元素，$\delta $表示状态转移，对应有向图中带箭头的边，$\delta (1,a)=2$表达状态1读入a后要跳转到状态2。\\
【运行机制】\\
一个 FA，若存在一条从某开始状态 i 到某结束状态 j 的通路，且这条通路上所有边的标记连成的符号串为$\alpha $，则$\alpha $就是一个句子；所有这样的$\alpha $的集合，就是该 FA 表示的语言。\\
如果一个自动机的起始状态和终止状态写在了一起，则表示这个自动机是能接受空串的。\\
从自动机的应用上来说，基本的功能是判断一个符号串能否被一个文法所接收，换句话来说，若能找到一个路径恰巧对应这个符号串，则表示该符号串能被接收，如果找不到这样的路径，则表示这个符号串不能被自动机所接收。\\
$\divideontimes$正规语言的三种表示法综合示例：
\begin{example}
    \label{ex:3.4}
    $\rm{L=\left\{a b^{n} c, b^{n} \mid n \geqslant 0\right\}, \sigma=\{a, b, c\}}$
\end{example}
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/9}
    \caption[]{综合示例}
    \label{fig:3.9}
\end{figure}
【注】 凡是能由上述三种方法表示的语言，一定是正规语言；反之，凡是不能由上述三种方法表示的语言，一定不是正规语言。
\section{有限自动机的定义与分类}
\subsection{有限自动机的定义}

\begin{definition}
    \label{def:3.2}
    有限自动机是一种数学模型，用于描述正规语言，可定义为\color{red}{五元组}\color{black}{:}$\mathrm{FA}=(\mathrm{Q}, \Sigma, \mathrm{S}, \mathrm{F}, \delta)$\\
上下文无关文法是几元组？四元组：非终结符集，终结符集，起始符号，产生式集合。有限自动机是五元组，\\
\end{definition}

Q(有限状态集);\\
$\Sigma$(字母表);\\
S(开始状态集,$S \subseteq Q$);\\
F(结束状态集,$F\subseteq Q$);\\
$\delta$:变换(二元函数):\\
状态$\circledtext{1}\circledtext{2}\circledtext{3}\circledtext{4}\circledtext{5}$用状态Q来表示，S是Q的子集,变换$\delta(i, a)=j$或$\circledtext{i}   \stackrel{\mathbf{a}}{\longrightarrow}\circledtext{j}$$\mathrm{i}, \mathrm{j} \in \mathrm{Q},
\mathrm{a} \in \sum+\{\boldsymbol{\varepsilon}\}$表示状态i遇符号a，变换为状态j。空串在应用的角度来说不好，给计算机处理带来很大的麻烦，但是有限自动机是可以读入空串的。
\subsection{有限自动机怎样描述语言}
令 L(FA)为自动机FA所描述的正规语言；则$L(F A)=\left\{x \mid(i \stackrel{x}{\Rightarrow} j), x \in \Sigma^{*}, i \in S, j \in F\right\}$\\
一个有限状态自动机FA所对应的语言写作L(FA)。从起始状态i到结束状态j的路径上所有符号所拼接起来构成的符号串便是该自动能接受的一个符号串，所有这样符号串构成的集合便是FA所对应的语言，记作L(FA)。$\mathrm{i} \stackrel{x}{\Rightarrow} \mathrm{j}$表示从起始状态i到终止状态j，其中每一次跳转分别读入的符号为a1、a2一直到$a_{n}$，写成这样的形式设$\mathbf{x}=\mathbf{a}_{1} \mathbf{a}_{2} \ldots \mathbf{a}_{n}, \quad \mathbf{a}_{i} \in \Sigma+\{\varepsilon\}$则有$i \stackrel{a_{1}}{\Rightarrow} i_{1} \stackrel{a_{2}}{\Rightarrow} i_{2} \ldots {\stackrel{a_{n}}\Rightarrow} j$,每次读入的字符构成了一个符号串$\mathbf{a}_{1} \mathbf{a}_{2} \ldots \mathbf{a}_{n}$,记为x，则符号串x是L（FA）中的一个句子，所有句子构成的集合就是该有限自动机对应的语言。\\
FA 存在一条从某初始状态 i 到某结束状态 j 的连续变换，且每次变换($\Rightarrow$)的边标记连成的符号串为 x ，则称x被FA接受，否则拒绝。\\
所以有限状态自动机最重要的一个功能是判断一个词串是否能被接收，词法分析便是利用有限状态自动机来识别单词串。
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/11}
    \caption[]{有限自动机}
    \label{fig:3.10}
\end{figure}
$\divideontimes$L(FA)的生成(或识别)过程示例：
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/12}
    \caption[]{L(FA)生成(或识别)过程示例}
    \label{fig:3.11}
\end{figure}
起始状态$\circledtext{1}$读入a跳转到$\circledtext{2} $号状态，$\circledtext{2}$号状态读入一个c到$\circledtext{3}$号状态，$\circledtext{3}$号状态是一个结束态，因此符号串ac是该语言的一个句子。\\
起始状态$\circledtext{1}$读入a跳转到$\circledtext{2}$号状态，$\circledtext{2}$号状态读入一个b仍然跳转到$\circledtext{2}$状态，$\circledtext{2}$状态读入c跳转到$\circledtext{3}$号状态，$\circledtext{3}$状态是个结束态，因此符号串abc是该语言的一个句子。\\
起始状态$\circledtext{1}$读入a跳转到$\circledtext{2}$号状态，$\circledtext{2}$号状态读入一个b仍然跳转到$\circledtext{2}$状态，$\circledtext{2}$号状态又读入一个b仍然跳转到$\circledtext{2}$状态，$\circledtext{2}$状态读入c跳转到$\circledtext{3}$号状态，$\circledtext{3}$状态是个结束态，因此符号串abbc是该语言的一个句子\\
综上，上半部分自动机FA1对应的语言可表示为$\therefore$$L(F A 1)=\left\{a b^{n} c \mid n \geqslant 0\right\}$\\
$\uppercase\expandafter{\romannumeral2}$.第二条通路：FA2\\
起始状态$\circledtext{1}$直接读入空串就到达了结束态。\\
起始状态$\circledtext{1}$读入b到达结束态$\circledtext{4}$。\\
起始状态$\circledtext{1}$读入b到达状态$\circledtext{4}$，再读入b又到了$\circledtext{4}$状态，这个时候是结束态。\\
以此类推，下半部分的自动机FA2 
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/13}
    \caption[]{FA自动机}
    \label{fig:3.12}
\end{figure}表达的是$\therefore L(F A 2)=\left\{b^{n} \mid n \geqslant 0\right\}$\\
因此整个自动机所对应的语言就是FA1和FA2对应的语言合并在一起，即$\therefore$$\rm{L(F A)=\left\{a b^{n} c \mid n \geqslant 0\right\}}$
\subsection{有限自动机的两种表现形式}

\begin{example}
    \label{ex:3.7}
    \noindent \color{red}{有限自动机}\color{black}{:}
    \color{red}{$\mathrm{FA}=(\mathrm{Q}, \Sigma, \mathrm{S}, \mathrm{F}, \delta)$}\\
    其中:\color{red}{Q}\color{black}{={1,2,3,4}},\color{red}{$\Sigma$}\color{black}{{a,b,c}},
    \color{red}{S}\color{black}{={1,2}},\color{red}{F}\color{black}{={3,4}}\\
    \color{red}{$\delta$}:\color{black}{$\delta(1,a)=2$;$\delta(1,b)=4$;$\delta(2,b)=2$;}\\
{$\delta(2,c)=3$;$\delta(2,\varepsilon)=3$;$\varepsilon(4,b)=4$;}\\
\end{example}


我们可以把有限自动机写成状态图或变换表的模式\\
FA 的两种表现形式：
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/14}
    \caption[]{FA状态图}
    \label{fig:3.13}
\end{figure}
这个图并不容易让计算机去识别
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/15}
    \caption[]{FA变换表}
    \label{fig:3.14}
\end{figure}
这是计算机存储中最常用的方式，可以把状态转移看成一个表的形式，表中每一行对应一个状态，所以这个表中写了四个状态，每一个列分别对应一个字母，行和列的交叉点表示对应的状态读入相应的字母时应跳转到的状态。
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/16}
    \caption[]{状态1}
    \label{fig:3.15}
\end{figure}
表达$\circledtext{1}$状态读入a跳转到$\circledtext{2}$状态，即$\delta(1,a)=2$\\
起始状态和结束状态分别用“+”和“-”表示。
$\divideontimes$有限自动机的构造示例1
\begin{example}
    \label{ex:3.8}
    $\rm{A=\left\{a b^{n} c,(a b)^{n} \mid n \geqslant 0\right\}}$FA的构造:
\end{example}
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/17}
    \caption[]{方法一}
    \label{fig:3.16}
\end{figure}
对于符号串$ab^{n}c$可构造出这样一个自动机，开始状态$\circledtext{1}$读入a进入$\circledtext{2}$状态，使用循环方式表示$\circledtext{2}$状态可读入无限个b,$\circledtext{2}$状态若读入c进入$\circledtext{3}$状态。同样道理第二个串$(ab)^{n}$可以写成这样的自动机，开始状态4读入a进入5状态，5状态读入b进入结束态4。注意4状态既是起始态又是结束态，表示该自动机可接收一个空串。
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/18}
    \caption[]{方法二}
    \label{fig:3.17}
\end{figure}
$\circledtext{4}$状态是一个起始状态，但是在方法二中$\circledtext{1}$状态通过 跳转到了$\circledtext{4}$状态，所以$\circledtext{4}$状态可以不标注起始状态。\\
消除$\circledtext{1}$状态到$\circledtext{4}$状态的$\varepsilon $跳转得到
 \begin{figure}[H]
    \centering
    \input{chapter3/figures/19}
    \caption[]{跳转结果}
    \label{fig:3.18}
\end{figure}
该自动机与联合式或组合式的自动机是否等价？答案：不等价\\
正确的自动机如图所示
\begin{figure}[H]
    \centering
    \input{chapter3/figures/20}
    \caption[]{正确结果}
    \label{fig:3.19}
\end{figure}
接下来比较各种自动机表示方法的优劣：方法一：开始状态不唯一,不好用!方法二：带有$\varepsilon$边，还是不好用!另外，变换函数不单值，如$\delta(1,a)=(2|4)$也不好用！
\begin{figure}[H]
    \centering
    \input{chapter3/figures/21}
    \caption[]{方法三}
    \label{fig:3.20}
\end{figure}
状态唯一，不带有$\varepsilon$边，变换函数单值的有限自动机。



%----------------------------------------------------------------------------------------
%蒙龙从这里开始转录
%----------------------------------------------------------------------------------------



最后我们再举一个现在中的例子：奇偶校验

\begin{example}[] %这里的图有点空，可能换成两个图在一行可能会好一点
    \label{ex:3.9}
    奇偶校验
    
    奇校验
    
    Input：由0，1组成的字符串
    
    Output：奇数个1，则输出ok，否则拒绝
    \begin{figure}[H]
        \centering
        \input{chapter3/figures/24}
        \caption[]{奇校验}
        \label{fig:3.21}
    \end{figure} 
    类似的，偶校验的自动机如下：
    \begin{figure}[H]
        \centering
        \input{chapter3/figures/25}
        \caption[]{偶校验}
        \label{fig:3.22}
    \end{figure} 
\end{example}

\subsection{有限自动机的分类}

\begin{enumerate}
    \setlength{\itemindent}{2em}
        \item 确定的有限自动机（DFA）

        特征：\circledtext{1}开始状态唯一；\circledtext{2}变换函数单值；\circledtext{3}不带$\varepsilon$边。

        \item 非确定的自动机（NFA）-- 不能全部具备上述特征者！

        \begin{enumerate} 
            \setlength{\itemindent}{2em}
            \item 带有$\varepsilon$边的非确定的有限自动机，记为$\varepsilon$NFA；
            \item 不带有$\varepsilon$边的非确定的有限自动机，记为$\bar{\varepsilon}$NFA；
        \end{enumerate}
\end{enumerate}
$\divideontimes$有限自动机的分类示例
\begin{example}[]
    \label{ex:3.10}
    试分别指出下述有限自动机的分类情况
    \begin{figure}[H]
        \centering
        \input{chapter3/figures/26}
        \caption[]{有限自动机的分类情况}
        \label{fig:3.23}
    \end{figure} 
\end{example}
上述五个有限状态自动机中哪些是确定型的？FA2为DFA。

FA4变换函数不单值，FA5起始状态不唯一，FA1和FA3带有$\varepsilon$边。

\section{有限自动机的等价变换}
能不能找到确定型的有限状态自动机，从理论上已经证明任何有限状态自动机都可以转化为确定型的有限状态自动机。
有限自动机的等价变换,是指把FA1变换为FA2,且有$\mathrm{L(FA1)=L(FA2)}$。主要包含以下两个内容：
\begin{enumerate} 
    \setlength{\itemindent}{2em}
        \item 有限自动机的确定化（$\mathrm{NFA=>DFA}$）;

        找到一个确定型有限状态自动机，同时其接收的语言和原始的自动机接收的语言是一摸一样的，这个过程叫确定化。
        非确定机（NFA）较易构造，但不易于使用。
        相反，确定机（DFA）较难构造，但使用上更加方便。

        $\divideontimes$任何一非确定机NFA,皆可通过有效算法把其转换为等价的确定自动机DFA。

        \item 有限自动机的化简（最小化）；

        找到一个自动机和原自动机是等价的，但其状态数是最少的。

        $\divideontimes$对任何一确定机DFA1,皆可通过有效算法将其转换为等价的确定机DFA2，且DFA2的状态最少。
\end{enumerate}

\subsection{有限自动机的确定化}
第一步先把一个含$\varepsilon$边的非确定有限状态自动机转化为不含$\varepsilon$边的非确定有限状态自动机，第二步把不含$\varepsilon$边的非确定有限状态自动机确定化。

1.消除$\varepsilon$边算法（$\varepsilon \mathrm{NFA} \Rightarrow \bar{\varepsilon} \mathrm{NFA}$或DFA）
\begin{enumerate} 
    \setlength{\itemindent}{2em}
        \item  若存在$\varepsilon$闭路，则把$\varepsilon$闭路上各节点合而为一：
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/27}
            \caption[]{$\varepsilon$闭路上各节点合而为一}
            \label{fig:3.24}
        \end{figure} 
        \item 标记隐含的开始态和结束态：
        
        开始态的ε通路上的节点：+

        结束态逆向ε通路上节点：-

        从起始状态开始找到所能到达的ε通路上的所有节点，将其标注为起始状态。比如起始状态\circledtext{1}，通过$\varepsilon$跳转到达的任何节点都标注为起始状态。

        从结束态逆向标注，如果一个节点通过$\varepsilon$跳转能到达结束态，则认为这个节点是结束态逆向通路上的节点，将其标记为结束态。

        例如：
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/28}
            \caption[]{标记隐含的开始态和结束态}
            \label{fig:3.25}
        \end{figure}
        起始状态\circledtext{1}通过$\varepsilon$跳转到\circledtext{3}状态，\circledtext{3}状态通过$\varepsilon$跳转到\circledtext{2}状态，因此\circledtext{3}状态和\circledtext{2}状态都是起始状态$\varepsilon$通路上的节点，将状态\circledtext{2}和状态\circledtext{3}标记为起始状态。同样道理，\circledtext{3}状态是结束态，\circledtext{1}状态通过$\varepsilon$跳转可以到达\circledtext{3}状态，因此将\circledtext{1}状态标记为结束状态。

        \item 对剩余的$\varepsilon$边，逆向逐一进行：
        
        \circledtext{1}删除一个$\varepsilon$边；同时

        \circledtext{2}引进新边：凡由原$\varepsilon$边终点出发的边，也要由其始点发出。

        \begin{figure}[H]
            \centering
            \input{chapter3/figures/29}
            \caption[]{删除$\varepsilon$边，同时引进新边}
            \label{fig:3.26}
        \end{figure}

        \item 重复步骤(3)，直到再无$\varepsilon$边为止。
        例如：
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/30}
            \caption[]{重复步骤(3)，直到再无$\varepsilon$边}
            \label{fig:3.27}
        \end{figure}
        删除状态\circledtext{2}到状态\circledtext{3}的$\varepsilon$边，\circledtext{3}状态能到达\circledtext{3}状态和\circledtext{5}状态，所以\circledtext{2}状态读入b也得到达\circledtext{3}状态，\circledtext{2}状态读入c也能到达\circledtext{5}状态。
\end{enumerate}

\begin{example}
    
    消除$\varepsilon$边算法示例：
    \label{ex:3.11}
\end{example}
    已知$\varepsilon$NFA如下，求$\mathrm{L(\varepsilon NFA)}=?$
    \begin{figure}[H]
        \centering
        \input{chapter3/figures/31}
        \caption[]{消除$\varepsilon$边算法示例}
        \label{fig:3.28}
    \end{figure}

    \begin{enumerate} 
        \setlength{\itemindent}{2em}
        \item $\varepsilon$闭路上的节点等价，（$\circledtext{1}\equiv\circledtext{2}$），可合二为一；得到
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/32}
            \caption[]{节点等价}
        \label{fig:3.29}
        \end{figure}

        \item 标记隐含的开始态和结束态：+\circledtext{4}，+\circledtext{3}，-\circledtext{1}

        从开始状态找$\varepsilon$通路，把通路上的节点都标为开始状态，\circledtext{1}状态读入$\varepsilon$到达\circledtext{4}状态，\circledtext{4}状态读入$\varepsilon$到达\circledtext{3}状态。从结束态开始，找$\varepsilon$逆向通路上的节点，将其标记为结束态，\circledtext{1}状态通过$\varepsilon$跳转到达结束态\circledtext{4}状态，所以将\circledtext{1}状态标记为结束态。

        \item 逆序逐一删除$\varepsilon$边，同时引进新边：
        
        先删除\circledtext{4}状态到\circledtext{3}状态的$\varepsilon$边
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/33}
            \caption[]{删除\circledtext{4}到\circledtext{3}的$\varepsilon$边}
        \label{fig:3.30}
        \end{figure}

        然后删除\circledtext{1}到\circledtext{4}的$\varepsilon$边
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/34}
            \caption[]{\circledtext{1}到\circledtext{4}的$\varepsilon$边}
        \label{fig:3.31}
        \end{figure}

        \circledtext{3}能到达\circledtext{4}，那\circledtext{4}就能到达\circledtext{4}（即\circledtext{3}能读入c到\circledtext{4}，那\circledtext{4}就能读入c到\circledtext{4}）
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/35}
            \caption[]{\circledtext{4}读入c到\circledtext{4}}
        \label{fig:3.32}
        \end{figure}

        删除状态\circledtext{1}到状态\circledtext{4}的$\varepsilon$边，④状态能到达\circledtext{4}状态，所以\circledtext{1}状态读入c也能到达\circledtext{4}状态
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/36}
            \caption[]{$\bar{\varepsilon}\mathrm{NFA}$}
        \label{fig:3.33}
        \end{figure}
    \end{enumerate}
    
    $\therefore \mathrm{L}(\bar{\varepsilon} \mathrm{NFA})=\{\mathrm{a^{m}, a^{m} b c^{n}, a^{m} c^{n}} \mid \mathrm{m} \geqslant 0, \mathrm{n} \geqslant 1\}$


2.$\bar{\varepsilon}\mathrm{NFA}$的确定化算法（$\bar{\varepsilon}\mathrm{NFA}\Rightarrow\mathrm{DFA}$）
\begin{enumerate} 
    \setlength{\itemindent}{2em}
        \item 构造DFA的变换表（框架）：
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/37}
            \caption[]{DFA变换表}
            \label{fig:3.34}
        \end{figure}
        \item 按$\bar{\varepsilon}\mathrm{NFA}$的变换函数实施变换：$\delta(\{q_{i}{ }^{1}, \ldots q_{i}{ }^{n}\}, a_{k})=\{q_{j}{ }^{1}, \ldots q_{j}{ }^{n}\}$
        \item 若$\{q_{i}{ }^{1}, \ldots q_{i}{ }^{n}\}$未作位状态进行标记，则作新行标记；
        \item 重复步骤(2)(3)，直到不再出现新状态集为止；
        \item 标记DFA的开始态和结束态：
        
        $\bullet$第一行$\{q_{i}{ }^{1}, \ldots q_{i}{ }^{n}\}$，（右侧）标记+；
        
        $\bullet$凡是状态行中含有$\bar{\varepsilon}\mathrm{NFA}$的结束状态者，（右侧）标记-。
\end{enumerate}

【注】必要时，新产生的DFA可用状态图表示。

自动机所有的起始状态构成一个集合$\{q_{i}{ }^{1}, \ldots q_{i}{ }^{n}\}$，该集合作为确定自动机DFA的起始状态。DFA变换表的行由原始自动机中状态或状态集合表示$\{q_{i}{ }^{1}, \ldots q_{i}{ }^{n}\}$，列是字母表上的符号。从DFA起始状态集合开始，把集合中任意一个状态读入相应的字母所到达的状态合成一个集合（到达的状态集合），作为DFA变换表中相应的表项，注意该表项可能是一个单一状态，也可能是一个状态集合。只要表项中状态或状态集合没有出现在DFA变换表的行标记中，则将其作为一个新的行标记，直到没有新的行标记出现为止。经过上述处理后，便可得到原始自动机对应的确定化有限自动机，这个确定化有限自动机的状态可能是是原始自动机中的状态或状态的集合。最后，标注开始态和结束态，新自动机的开始态只有一个，即$\{q_{i}{ }^{1}, \ldots q_{i}{ }^{n}\}$；如果新自动机中行标记包含原始自动机的结束态，就将其都标记为结束态。

$\divideontimes\bar{\varepsilon}\mathrm{NFA}$确定化示例

\begin{example}
    \label{ex:3.12}
\end{example}
    联合自动机NFA：
    
    \begin{figure}[H]
        \centering
        \input{chapter3/figures/38-1}
        \caption[]{联合自动机NFA}
        \label{fig:3.35}
    \end{figure}

    不是确定型的自动机 %具体需要看看是不是这么些

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/38-2}
        \caption[]{确定化过程}
        \label{fig:3.36}
    \end{figure}

    【注】A,B,C,… 状态集的代码

    表列是字母表，行对应的是状态，原始自动机的起始状态\circledtext{1}\circledtext{4}作为确定自动机的起始状态，读入a到达\circledtext{2}\circledtext{5}
    
    B\{2,5\}读入b到达C\{2,4\} 读入c到达D\{3\}；
    
    C\{2,4\}读入a到达E\{5\} 读入b到达F\{2\} 读入c到达D\{3\}；
    
    E\{5\}读入b到达G\{4\}；
    
    F\{2\}读入b到F\{2\} 读入c到D\{3\}；
    
    G\{4\}读入a到E\{5\}；
    
    只要新自动机中行标记包含原始自动机的结束态，就将其都标记为结束态。
    
    根据确定自动机的变换表，便可构造出该确定自动机对应的状态图，不难看出，这两个自动机是等价的。


\subsection{有限自动机的最小化}
有限自动机的最小化,又称有限自动机的化简，是指对给定的确定机DFA1,构造另一个确定机DFA2,使得 $\mathrm{L(DFA1)=L(DFA2)}$,且DFA2的状态最少。

有限自动机最小化算法，是指构造满足下述条件的确定有限自动机(称为最小机)：

\begin{enumerate} 
    \setlength{\itemindent}{2em}
        \item 删除无用状态；
        \item 合并等价状态。
\end{enumerate}

第一步是删除无用状态

\begin{definition}
    \label{def:3.3}
    无用状态是指由开始态达不到的状态(不可达)或者由其出发不能到达结束态的状态(不终结)。
\end{definition}

无用状态是指两种状态，一种是不可达的状态，一种是不终结的状态。这两种状态是不会参与到自动机的运行里的，参与了也没有用，所以这两种状态是不需要的，可以删除掉。
第二步是合并等价状态。

如果两个状态是等价的，这两个状态是可以在最小化的操作中被合并的。那什么是等价状态呢？

\begin{definition}
    \label{def:3.4}
    等价状态是指这样的两个状态，若分别将其看作开始态，二者接收的符号串集合相同。
\end{definition}

下面我们来看一个例子

\begin{example}[]
    \label{ex:3.13}
    无用状态
    
    \begin{figure}[H]
        \centering
        \input{chapter3/figures/39}
        \caption[]{不可达状态}
        \label{fig:3.37}
    \end{figure}

    状态\circledtext{4}只有出边没有入边，所以该状态是一个不可达状态。

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/40}
        \caption[]{不终结状态}
        \label{fig:3.38}
    \end{figure}

    状态\circledtext{3}只有入边，没有出边，所以该状态是一个不终结状态。

    不管是不可达也好，还是不终结也好，这两个状态都不是自动机需要的状态。
\end{example}

我们再来看下一个例子：

\begin{example}[]
    \label{ex:3.14}
    合并等价节点
    
    \begin{figure}[H]
        \centering
        \input{chapter3/figures/41}
        \caption[]{合并等价节点}
        \label{fig:3.39}
    \end{figure}
    
    状态\circledtext{2}和状态\circledtext{3}这两个状态可以通过读入空串来互相跳转，\circledtext{2}通过读入空串跳转到\circledtext{3}，\circledtext{3}通过读入空串跳转到\circledtext{2}。之前说过，这是一个带空边的闭环，所以在这个闭环上的所有节点都是等价的，因此可以把它们合二为一。

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/42}
        \caption[]{保留非空跳转}
        \label{fig:3.40}
    \end{figure}

    可以看到，合并之后的\circledtext{2}状态可以通过读b跳转到\circledtext{2}，可以通过读c跳转到\circledtext{2}，这是因为\circledtext{2}\circledtext{3}合并之后，\circledtext{2}和\circledtext{3}上的非空跳转仍然需要保留。
\end{example}

接下来看下一个例子，如何去判断等价性。上面例子中的带空边闭环是比较好判断的。

\begin{example}[]
    \label{ex:3.15}
    如何判断等价性：
    
    \begin{figure}[H]
        \centering
        \input{chapter3/figures/43}
        \caption[]{判断等价性}
        \label{fig:3.41}
    \end{figure}

    首先判断\circledtext{4}和\circledtext{5}是否是等价的，我们可以从定义出发：
    
    等价状态是指这样的两个状态，若分别将其看作开始态，二者接收的符号串集合相同。
    如果同样把\circledtext{4}和\circledtext{5}看做开始态，可以看到\circledtext{4}状态可以接收空边到\circledtext{2}，\circledtext{2}再接收a到\circledtext{4}，\circledtext{4}还可以接收b到结束态\circledtext{5}，即\circledtext{4}作为开始态可以接收符号串ab，但是\circledtext{5}作为开始态并不可以接收符号串ab。所以\circledtext{4}和\circledtext{5}是不等价的。

    第二个问题：\circledtext{3}和\circledtext{5}是否是等价的？
    
    状态\circledtext{3}和\circledtext{5}都是终止态，这两个状态都不能接收任何符号串，所以状态\circledtext{3}和状态\circledtext{5}是等价的。

    第三个问题，\circledtext{2}和\circledtext{3}是否是等价？
    
    显然\circledtext{2}状态能够读入a到\circledtext{3}状态，而\circledtext{3}状态不能接收任何符号串，所以这两个状态是不等价的。

    最后一个问题，\circledtext{2}和\circledtext{4}是否是等价？
    
    \circledtext{4}状态能够接收b到结束态\circledtext{5}，而\circledtext{2}状态不能接收b，所以这两个状态也不是等价的。
\end{example}

【算法】%感觉有点奇怪，之前好像没有这么写的

接下来我们看一下如何去执行这两步：删除无用状态以及合并等价状态。首先看删除无用状态的算法。删除无用状态我们在这给了两个算法，第一个是删除不可达状态。

$\divideontimes$【删除不可达状态】构造可达状态集$\mathrm{Q_{AR}}$

\begin{enumerate} 
    \setlength{\itemindent}{2em}
        \item 设$\mathrm{q_{0}}$为开始态，则令$\mathrm{q_{0}}\in\mathrm{Q_{AR}}$；
        \item 若$\mathrm{q_{i}}\in\mathrm{Q_{AR}}$且有$\delta(\mathrm{q_{i}, a})=\mathrm{q_{j}}$则令$\mathrm{q_{j}}\in\mathrm{Q_{AR}}$；
        \item 重复执行(2)，直到$\mathrm{Q_{AR}}$不再增大为止。
        \item 从状态集$\mathrm{Q}$中，删除不在$\mathrm{Q_{AR}}$中的所有状态。
\end{enumerate}

首先要理解什么是不可达状态？就是无法到达的状态。那么为什么不可达呢？这个不太好描述，我们可以反过来想想，什么是可达的状态。可达状态的定义非常简单，从起始状态开始，只要能找到一条路径到达一个状态，那么这个状态就是可达状态。从这个角度说，是否可以找出一个可达状态的集合呢？这个算法就告诉我们怎么去构造可达状态集合。

首先从起始状态开始，不断的进行搜索，将所有可达的状态都加入到集合当中，最后当这个集合不再增加的时候，就得到了可达状态集合，从状态集中把这些状态删除，就得到了不可达状态的集合。

同样的道理，不终结的状态怎么判断呢？类似的，不好判断一个状态是否是不终结状态，我们可以去想想什么节点能够终结？那就是什么节点能够到达终止状态，如果可以找出所有能够到达终止状态的节点，那么其余状态便是不终结状态。

$\divideontimes$【删除不终结状态】构造可终结状态集$\mathrm{Q_{FN}}$

\begin{enumerate} 
    \setlength{\itemindent}{2em}
        \item 设$\mathrm{q_{i}}$为结束态，则令$\mathrm{q_{i}}\in\mathrm{Q_{FN}}$；
        \item 若$\mathrm{q_{j}}\in\mathrm{Q_{FN}}$且有$\delta(\mathrm{q_{i}, a})=\mathrm{q_{j}}$则令$\mathrm{q_{i}}\in\mathrm{Q_{FN}}$；
        \item 重复执行(2)，直到$\mathrm{Q_{FN}}$不再增大为止。
        \item 从状态集$\mathrm{Q}$中，删除不在$\mathrm{Q_{FN}}$中的所有状态。
\end{enumerate}

接下来看一下如何判断等价状态。首先，两个状态i,j等价，当且仅当满足下面两个条件：

\begin{enumerate} 
    \setlength{\itemindent}{2em}
        \item 必须同是结束态，或同不是结束态；
        \item 对所有字母表上符号，状态i,j必变换到等价状态。
\end{enumerate}

第一个条件，两个状态必须同是结束态，或者同不是结束态，如果这两个状态里有一个是结束态，有一个不是结束态，显然结束态的那个节点可以读空直接停止了，而非结束态的不一定。

第二个条件，对于字母表上的所有符号，两个状态分别读入同一个字符跳转到的两个状态都应该是等价状态。例如，i状态读入a跳转到I’,j状态读入a跳转到J’，如果I’和J’等价，那么i,j也是等价的。

\begin{example}[]
    \label{ex:3.16}
    判断等价状态：

    把下述自动机最小化 %这里题目有点不清楚
    \begin{figure}[H]
        \centering
        \input{chapter3/figures/44}
        \caption[]{判断等价状态}
        \label{fig:3.42}
    \end{figure}

    \begin{enumerate} 
        \setlength{\itemindent}{2em}
        \item 初分成两个不等价子集：$\mathrm{Q_{1}=\{1,2\}}$，$\mathrm{Q_{2}=\{3\}}$

        将状态分为两个不等价子集，根据等价条件的第一个条件，因为\circledtext{1}，\circledtext{2}状态都是结束态，而\circledtext{3}状态不是结束态，可以划分成两个不等价子集{1，2}和{3}。这一步只能说\circledtext{1}，\circledtext{2}有可能是等价，但是\circledtext{1}跟3或者\circledtext{2}跟\circledtext{3}肯定不是等价的。

        接下来第二步，根据等价条件的第二个条件，如果两个状态读入相同的字符，都能跳转到等价状态，那么这两个状态是等价的。状态\circledtext{1}，\circledtext{2}同时读入a，b都能跳转到同一个状态，因此\circledtext{1}，\circledtext{2}等价。

        \item 还能分成不等价子集吗?\\
        $\because\delta(\{1,2\},\mathrm{a})=2$\\
        又$\delta(\{1,2\},\mathrm{b})=3$\\
        $\therefore 1 \equiv 2$

        所以可以将\circledtext{1}，\circledtext{2}状态合并在一起，得到了下面的自动机

        \begin{figure}[H]
            \centering
            \input{chapter3/figures/45}
            \caption[]{将\circledtext{1}，\circledtext{2}状态合并}
            \label{fig:3.43}
        \end{figure}
    \end{enumerate}
\end{example}

我们可以将上述步骤总结成一个算法：

【合并等价状态算法】-- 划分不等价状态集

\begin{enumerate} 
    \setlength{\itemindent}{2em}
        \item 初始，把状态集Q化分成两个不等价子集：
        
        $\mathrm{Q_{1}}$（结束状态集）， $\mathrm{Q_{2}}$（非结束状态集）；
        
        \item 把每个$\mathrm{Q_{i}}$再划分成不同的子集，条件是：

        同一$\mathrm{Q_{i}}$中两个状态i，j，若对字母表中的某个符号，变换到已划分的不同的状态集中，则i，j应分离，如：$\delta(\mathrm{i,a})\in \mathrm{Q_{m}},\delta(\mathrm{j,a})\in \mathrm{Q_{n}}$且$\mathrm{m}\ne\mathrm{n}$

        \item 重复步骤(2)，直到再不能划分为止；

        \item 合并最终划分的每个子集中的状态（合而为一）。
\end{enumerate}


%----------------------------------------------------------------------------------------
% 从这开始是3.3.2节的后半部分
%----------------------------------------------------------------------------------------


\begin{example}[]
    \label{ex:3.17}
    $\divideontimes$有限自动机化简示例：
\end{example}

\begin{figure}[H]
    \centering
    \input{chapter3/figures/46}
    \caption[]{DFA}
    \label{fig:3.44}
\end{figure}

第一步：删除无用状态

动态构造DFA变换表，即从开始状态 1 出发，把变换后的状态填入表项，并同时作为新行标记；
如此下去，直到不再出现新状态为止。未出现的状态，就是无用的状态。

\begin{figure}[H]
    \centering
    \input{chapter3/figures/47}
    \caption[]{构造DFA变换表}
    \label{fig:3.45}
\end{figure}

例\ref{ex:3.17}对应的DFA变换表如上图所示，该表中状态便是所有的可达状态，
状态2和8不在里面，所以状态2和8是不可达状态。在这里我们分析的是不可达状态，不终结状态可以采用类似的方法来分析，
最终删除的不可达和不终结状态是2状态和8状态。

第二步：合并等价状态

\begin{figure}[H]
    \centering
    \input{chapter3/figures/48}
    \caption[]{DFA变换表}
    \label{fig:3.46}
\end{figure}

\begin{enumerate} 
    \setlength{\itemindent}{2em}
        \item 先将原始的状态划分为两个状态集，一个是结束状态集，另一个是非结束状态集。
        从变换表可以看出来结束态是5，6，7，所以把{5，6，7}划分为一个状态集，剩余的{1，3，4}是非结束状态集。
        
        令$\rm{Q_{NE={{1,3,4},{5,6,7}}}}$

        \item 第二步逐一去访问当前等价状态集合中的任意两个状态，
        如果它们读入同一个字符后跳转到的状态不在同一个等价状态集合里，则把它们分裂到不同的等价集中。
        
        取\{3,4\}：
        $$\because \delta (1,a) = 6, \delta ({3,4},a)=\{1,4\}$$
        $$\rm{\therefore \text{划分成} Q_1=\{1\},Q_2=\{3,4\}}\\$$
        $$ \rm{\text{即} Q_{NE}=\{\{1\},\{3,4\},\{5,6,7\}\}}\\$$
        首先看{1，3，4}状态集，由于状态1遇到a跳转到状态6，{3，4}遇到a跳转到状态{1,4}，
        其中状态6和{1，4}在不同的等价集合中，即6在{5，6，7}中，{3，4}在{1，3，4}中，所以把{1}和{3，4}分裂成不同的等价状态集。
        在这一步，我们可知状态1和状态3，状态4肯定不等价，但是状态3，状态4是否等价我们还不知道，还得继续去执行算法。
        
        \item 下一步我们看{3，4}，来确认状态3和状态4是否等价。
        
        由于状态3遇到a变成状态1，状态4遇到a变成状态4，由于状态1,状态4在不同的等价划分里，
        所以状态3和状态4肯定不是等价状态。因此，得到了新的等价集合{3}和{4}。

        \item 第四步继续对{5，6，7}执行算法。
        
        取\{5,6,7\}：同理，可划分成$\rm{Q_1=\{5\},Q_2=\{6,7\}}$

        最后：$\rm{Q_{NE}=\{\{1\},\{3\},\{4\},\{5\},\{6,7\}\}}$

        需要注意的是，划分等价状态集算法适用于不含空边的自动机。若自动机带有空边，可以先用之前学过的算法消空边，
        接下来再执行划分等价状态集算法。

        \item 最后得到了状态6和状态7是等价状态，因此只需要将6，7合并，如何合并呢？只需要将6替换7，得到的结果如下所示：
        
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/49}
            \caption[]{合并等价状态}
            \label{fig:3.47}
        \end{figure}        

        \item 最后将转化表变为自动机。
        
        \begin{figure}[H]
            \centering
            \input{chapter3/figures/50}
            \caption[]{最小的DFA}
            \label{fig:3.48}
        \end{figure} 

\end{enumerate}

\section{正规语言描述方法间的相互转换}

正规语言有三种等价的表示方法：

\begin{enumerate} 
    \setlength{\itemindent}{1em}
        \item 正规文法
        \item 正规式
        \item 有限自动机
\end{enumerate}

任何一个表示方法都能转化为另外两个，我们先看看正规文法和确定有限状态自动机之间的转换方法。

设$\rm{G(Z)=(V_N,V_T,Z,P),DFA=(Q,\sum,s,F,\delta )}$
正规文法是一个四元组，确定有限状态自动机是一个五元组，可以发现二者之间是有对应关系的，如下图所示：

\begin{figure}[H]
    \centering
    \input{chapter3/figures/51}
    \caption[]{正规文法与DFA之间的对应关系}
    \label{fig:3.49}
\end{figure} 

\begin{example}[]
    \label{ex:3.18}
    自动机$\Rightarrow$正规文法：

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/52}
        \caption[]{DFA}
        \label{fig:3.50}
    \end{figure} 

    令Z=\circledtext{1}，A=\circledtext{2},B=\circledtext{3}，则有正规文法
    $$\mathrm{G(Z):Z\to aA\mid cB,A\to bA\mid dB,B\to \varepsilon }$$
    
    根据上面的对应关系，可以基于自动机写出正规文法。

    相反，我们也能够将正规文法转为自动机：
\end{example}

\begin{example}[]
    \label{ex:3.19}
    正规文法$\Rightarrow$自动机，并求L(G)：
    \begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法规则]
    $$\mathrm{G(Z):Z\to aZ\mid bA\mid\varepsilon ,A\to bA\mid d}$$
    \end{tcolorbox}
    

    首先第一步，$\mathrm{A\to d}$ ，根据上面的对应规则，我们先做一点点变换：

    将 $\mathrm{A\to d}$变换为 $\mathrm{A\to dB, B\to \varepsilon}$。

    这一步的目的是什么？是希望让B作为终止态，显性体现在自动机里，
    经过上述变换后得到一个新的等价文法，唯一的区别是新文法中引入了一个非终结符B。
    $$\mathrm{\therefore G^`(Z)\text{与$G(Z)$等价}:}$$
    $$\mathrm{Z\to aZ\mid bA\mid \varepsilon , A\to bA\mid dB,B\to \varepsilon}$$

    之后令状态\circledtext{1}表示Z , 状态\circledtext{2}表示A, 状态\circledtext{3}表示B，画出自动机。

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/53}
        \caption[]{DFA}
        \label{fig:3.51}
    \end{figure} 

    这个文法对应的语言为：
    $$\mathrm{L(G)=\{\varepsilon , a^mb^nd\mid m\geqslant 0,n>0 \}}$$

\end{example}

接下来，我们来看一下正规式和有限自动机状态机的转换。

转换的机制如下：

设$e$为正规式，$\mathrm{DFA=(Q,\sum,s,F,\delta )}$，转换机制：

\begin{figure}[H]
    \centering
    \input{chapter3/figures/54}
    \caption[]{转换机制}
    \label{fig:3.52}
\end{figure} 

对于正规式$e$，可以看作是一个符号串，我们希望有一个自动机，能够从初始状态读入这个符号串，到达终止状态，这就完成了转化的过程。

\begin{definition}
    \label{def:3.5}
    符号串转换为DFA的过程称为分解，DFA转换为符号串的过程称为合成。
\end{definition}

以下是转换的规则，图中正方向称为分解过程，负方向称为合成过程：

\begin{figure}[H]
    \centering
    \input{chapter3/figures/55}
    \caption[]{转换规则}
    \label{fig:3.53}
\end{figure} 

而对于闭包型正规式，有如下5种转换方式：

\begin{figure}[H]
    \centering
    \input{chapter3/figures/56}
    \caption[]{闭包型正规式转换规则}
    \label{fig:3.54}
\end{figure} 

\begin{example}
    \label{ex:3.20}
    正规式$\Rightarrow $自动机：
    
    设$e=a^*b\mid bc^*$

    首先根据上述的转化规则转化为一个初始的自动机：

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/57-1}
        \caption[]{初始自动机}
        \label{fig:3.55}
    \end{figure} 

    经过一次分解后自动机变为：

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/57-2}
        \caption[]{一次分解后自动机}
        \label{fig:3.56}
    \end{figure} 

    对闭包型正规式分解后变为：

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/57-3}
        \caption[]{完全分解后自动机}
        \label{fig:3.57}
    \end{figure} 

    之后需要对这个带空边的自动机进行确定化，怎么进行确定化呢?
    先标记起始状态和终止状态，从起始状态开始，经过空边到达的所有节点都标记为起始状态，
    同样，所有通过空边到达终止状态的节点都标记为终止状态。然后逆向消除空边，第一次消除空边后变成这样：

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/59}
        \caption[]{消除一条空边的自动机}
        \label{fig:3.58}
    \end{figure} 

    消除第二个空边变成下面这样：

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/60}
        \caption[]{消除第二条空边的自动机}
        \label{fig:3.59}
    \end{figure}

    由于有\circledtext{1} \circledtext{2}两个起始状态，我们需要进一步进行确定化，用自动机确定化算法，构造出如下表所示的确定自动机的变换表。
    
    \begin{figure}[H]
        \centering
        \input{chapter3/figures/61}
        \caption[]{自动机变换表}
        \label{fig:3.60}
    \end{figure}

    最终得到了确定化后的自动机：

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/62-1}
        \caption[]{确定化后的状态机}
        \label{fig:3.61}
    \end{figure}

    由变换表\ref{fig:3.60}可知，C、E状态等价，最小化后的状态机如下图所示：

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/62-2}
        \caption[]{最小化后的自动机}
        \label{fig:3.62}
    \end{figure}

\end{example}

\section{有限状态自动机的实现问题}

在实际应用时，怎么去设计一个自动机呢？自动机的设计有以下两个说明：

\begin{enumerate}[]
    \setlength{\itemindent}{2em}
    \item 假定自动机只作为识别器，即对待识别的符号串仅回答:是(接受)或 否(拒绝)。 

    自动机其实就是这么一个装置，对任意的一个字符串，能接受就是yes，不能就是no。

    \item 为了便于处理，可令$\ooalign{$\bigvee$\cr$-$}$作为待识别的符号串的泛指后继符。
    
    我们将这个符号作为符号串的后继符，这个后继符怎么去理解呢？可以理解成把一个字符串的结尾单独用一个符号来表示。

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/63}
        \caption[]{扩展后的自动机}
        \label{fig:3.63}
    \end{figure}

    扩展之后的自动机如上图所示，只有唯一的开始态和唯一的结束态。当然我们可以将自动机表示成一个变换表，其中no代表不能接受的后继字符。

    \begin{figure}[H]
        \centering
        \input{chapter3/figures/64}
        \caption[]{自动机变换表}
        \label{fig:3.64}
    \end{figure}

\end{enumerate}

\subsection{控制程序设计}

基于上面的说明，给出一个自动机的控制程序流程图：

\begin{figure}[H]
    \centering
    \input{chapter3/figures/65}
    \caption[]{自动机控制程序流程图}
    \label{fig:3.65}
\end{figure}

\subsection{变换表存贮结构设计}

下面将解决状态转移表即变换表存储的问题，可以有很多存储状态转移表的方式：

\begin{enumerate} 
    \setlength{\itemindent}{2em}
    \item 二维数组 ，其下标是(状态，输入符号）；
    
    $\divideontimes $  为了适应不同编码语言的需要，状态和输入符号可采取相应的编码形式；通常，使用连续的正整数：0,1,2,3,…。

    二维数组的方式优点是简洁、访问快，提供下标就能直接访问。但是缺点是太占空间。

    \item  压缩变换表，方法是把每个状态行作为子表，状态为索引，并把错误的输入符号合并在一起,如下图所示,
    图中$\forall $（其他）代表错误符号，左侧蓝色索引表中的序号代表数字，右侧红色表为变换子表：
    
    \begin{figure}[h]
        \centering
        \input{chapter3/figures/66}
        \caption[]{压缩变换表}
        \label{fig:3.66}
    \end{figure}
    我们一般用第二种方法，索引表的形式。
    \begin{example}[]
        \label{ex:3.21}
        $\divideontimes $有限自动机实现示例：

        有限自动机DFA: 

        \begin{figure}[H]
            \centering
            \input{chapter3/figures/67}
            \caption[]{DFA}
            \label{fig:3.67}
        \end{figure}

        根据这个有限状态自动机，我们可以用上述的压缩变换表的形式存储自动机状态转移表。

        \begin{figure}[H]
            \centering
            \input{chapter3/figures/68}
            \caption[]{自动机状态转移表}
            \label{fig:3.68}
        \end{figure}

        最后，模拟一下应用压缩变换表的自动机的识别字符串的过程：

        \begin{figure}[H]
            \centering
            \input{chapter3/figures/69}
            \caption[]{字符串识别过程}
            \label{fig:3.69}
        \end{figure}

    \end{example}
    
\end{enumerate}

